The present invention relates to data processing by digital computer, and more particularly to computer systems, programs, and methods for addressing data in databases.
Database systems commonly allocate data space in fixed-sized pages that are generally a few kilobytes in size. Variable-sized data objects are stored in these pages. Databases are usually not static—the data objects are often modified, changed in size, deleted, moved to other data pages, and so on. Data objects can contain references to other data objects. For these reasons, databases require some form of data object identifier and an addressing scheme.
Generally, addressing data objects in a database (e.g., table rows) using object identifiers (e.g., in table indices) can be done in two ways; using either a physical address or a logical object identifier for the data object. Storing the physical address has obvious problems. For example, when the data object is moved to a different location in the database, the database system must update references to the data object in all other data objects that point to the moved data object. Alternatively, the database system must add a secondary reference to the data object in the original storage location, thereby extending the path needed to find the data object, which makes retrieving the data object less efficient and consumes space in the original storage location.
Using logical identifiers frees the database system from the need to update all references to the data object or store a secondary reference in the original storage location. The trade off is the cost of navigating some form of mapping structure, which must be updated whenever a data object is moved, that maps the logical identifier to the physical address. Some systems, for example, assign sequential identifiers to data objects and use B*-trees or multi-level mapping arrays to address the data objects.